package mo.leetcode_top;

import java.util.PriorityQueue;

public class L1926 {

    public int minStoneSum(int[] piles, int k) {
        PriorityQueue<Integer> max = new PriorityQueue<>((x, y) -> (y -x));
        int sum = 0;
        for (int pile : piles) {
            sum += pile;
            max.offer(pile);
        }
        while (k > 0) {
            @SuppressWarnings("ConstantConditions")
            int top = max.poll();
            int remove = top / 2;
            int left = top - remove;
            sum -= remove;
            max.offer(left);
            k--;
        }
        return sum;
    }

    public int minStoneSum2(int[] piles, int k) {
        int[] count = new int[10001];
        for (int pile : piles) {
            count[pile]++;
        }
        int sum = 0;
        int i = 10000;
        while (i >= 1) {
            if (count[i] == 0) {
                i--;
                continue;
            } else if (k > 0) {
                int min = Math.min(k, count[i]);
                count[i] -= min;
                count[i - i / 2] += min;
                sum += count[i] * i;
                k -= min;
                i--;
            } else {
                sum += i * count[i];
                i--;
            }
        }
        return sum;
    }

}
